home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / kernel / utils / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  4.0 KB  |  143 lines
  1. /* hash.h --
  2.  *
  3.  *     This file contains definitions used by the hash module,
  4.  *     which maintains hash tables.
  5.  *
  6.  * Copyright 1986 Regents of the University of California
  7.  * All rights reserved.
  8.  *
  9.  * $Header: /cdrom/src/kernel/Cvsroot/kernel/utils/hash.h,v 9.1 90/09/11 14:11:32 kupfer Exp $ SPRITE (Berkeley)
  10.  */
  11.  
  12.  
  13. #ifndef    _HASH
  14. #define    _HASH
  15.  
  16. #include "list.h"
  17.  
  18. /*
  19.  * Each hash bucket consists of a version number for the hash chain and
  20.  * a hash chain list header.
  21.  */
  22.  
  23. typedef struct Hash_Bucket {
  24.     int        version;
  25.     List_Links    list;
  26. } Hash_Bucket;
  27.  
  28. /*
  29.  * The following defines one entry in the hash table.
  30.  */
  31.  
  32. typedef struct Hash_Entry {
  33.     List_Links    links;
  34.     Address    value;        /* Pointer to anything. */
  35.     Hash_Bucket    *bucketPtr;    /* Pointer to hash bucket that this entry is
  36.                  * in. */
  37.     union {
  38.     Address     ptr;        /* One-word key value to identify entry. */
  39.     unsigned words[1];    /* N-word key value.  Note: the actual
  40.                  * size may be longer if necessary to hold
  41.                  * the entire key.
  42.                  */
  43.     char      name[4];    /* Text name of this entry.  Note: the
  44.                  * actual size may be longer if necessary
  45.                  * to hold the whole string. This MUST be
  46.                  * the last entry in the structure!!!
  47.                  */
  48.     } key;
  49. } Hash_Entry;
  50.  
  51. /*
  52.  * A hash table consists of an array of pointers to hash
  53.  * lists.  Tables can be organized in either of three ways, depending
  54.  * on the type of comparison keys:
  55.  *
  56.  *    Strings:      these are NULL-terminated; their address
  57.  *              is passed to HashFind as a (char *).
  58.  *    Single-word keys: these may be anything, but must be passed
  59.  *              to Hash_Find as an Address.
  60.  *    Multi-word keys:  these may also be anything; their address
  61.  *              is passed to HashFind as an Address.
  62.  *
  63.  *    Single-word keys are fastest, but most restrictive.
  64.  */
  65.  
  66. #define HASH_STRING_KEYS    0
  67. #define HASH_ONE_WORD_KEYS    1
  68.  
  69. typedef struct Hash_Table {
  70.     Hash_Bucket     *table;        /* Pointer to array of List_Links. */
  71.     int         size;        /* Actual size of array. */
  72.     int            version;    /* Version of the hash table.  Goes up
  73.                      * every time hash table grows. */
  74.     int         numEntries;    /* Number of entries in the table. */
  75.     int         downShift;    /* Shift count, used in hashing
  76.                      * function. */
  77.     int         mask;        /* Used to select bits for hashing. */
  78.     int         ptrKeys;    /* 1 means that keys (h_names) are
  79.                      * 1-word values (char *'s).  0 means
  80.                      * keys are strings.  >1 means keys
  81.                      * are ht_ptrKeys-word values.  */
  82. } Hash_Table;
  83.  
  84. /*
  85.  * The following structure is used by the searching routines
  86.  * to record where we are in the search.
  87.  */
  88.  
  89. typedef struct Hash_Search {
  90.     int     nextIndex;    /* Next bucket to check (after current). */
  91.     int        bucketVersion;    /* Version of the bucket currently being
  92.                  * searched.*/
  93.     int        tableVersion;    /* The version of the table being searched. */
  94.     Hash_Entry     *hashEntryPtr;    /* Next entry to check in current bucket. */
  95.     List_Links    *hashList;    /* Hash chain that are currently checking. */
  96. } Hash_Search;
  97.  
  98. /*
  99.  * Macros.
  100.  */
  101.  
  102. /*
  103.  * char * Hash_GetValue(h)
  104.  *     HashEntry *h;
  105.  */
  106.  
  107. #define Hash_GetValue(h) ((h)->value)
  108.  
  109. /*
  110.  * Hash_SetValue(h, val);
  111.  *     HashEntry *h;
  112.  *     char *val;
  113.  */
  114.  
  115. #define Hash_SetValue(h, val) ((h)->value = (Address) (val))
  116.  
  117. /*
  118.  * Hash_Size(n) returns the number of words in an object of n bytes
  119.  */
  120.  
  121. #define    Hash_Size(n)    (((n) + sizeof (unsigned) - 1) / sizeof (unsigned))
  122.  
  123. /*
  124.  * The following procedure declarations and macros
  125.  * are the only things that should be needed outside
  126.  * the implementation code.
  127.  */
  128.  
  129. extern void         Hash_Init _ARGS_((Hash_Table *table, int numBuckets,
  130.                       int ptrKeys));
  131. extern void        Hash_Stats _ARGS_((Hash_Table *table));
  132. extern void        Hash_Kill _ARGS_((Hash_Table *table));
  133. extern Hash_Entry     *Hash_Find _ARGS_((Hash_Table *table, Address key));
  134. extern Hash_Entry     *Hash_LookOnly _ARGS_((Hash_Table *table,
  135.                            Address key));
  136. extern void         Hash_Delete _ARGS_((Hash_Table *table,
  137.                         Hash_Entry *hashEntryPtr));
  138. extern void         Hash_StartSearch _ARGS_((Hash_Search *hashSearchPtr));
  139. extern Hash_Entry    *Hash_Next _ARGS_((Hash_Table *table,
  140.                        Hash_Search *hashSearchPtr));
  141.  
  142. #endif /* _HASH */
  143.